package InternetHax;
//translated from C++
// HERE THERE BE DRAGONS
import java.util.Vector;

public class Pathfinder {

    final int mapWidth = 60,  mapHeight = 60,  numberPeople = 3;
    int onClosedList = 10;
    final int notfinished = 0,  notStarted = 0;// path-related finalants
    final static int found = 1,  nonexistent = 2;
    final static int walkable = 0,  unwalkable = 1;// walkability array finalants
    //Create needed arrays
    Tile maptiles[][] = new Tile[0][0];// = new char [mapWidth][mapHeight];
    int openList[] = new int[mapWidth * mapHeight + 2]; //1 dimensional array holding ID# of open list items
    int whichList[][] = new int[mapWidth + 1][mapHeight + 1];  //2 dimensional array used to record 
// 		whether a cell is on the open list or on the closed list.
    int openX[] = new int[mapWidth * mapHeight + 2]; //1d array stores the x location of an item on the open list
    int openY[] = new int[mapWidth * mapHeight + 2]; //1d array stores the y location of an item on the open list
    int parentX[][] = new int[mapWidth + 1][mapHeight + 1]; //2d array to store parent of each cell (x)
    int parentY[][] = new int[mapWidth + 1][mapHeight + 1]; //2d array to store parent of each cell (y)
    int Fcost[] = new int[mapWidth * mapHeight + 2];	//1d array to store F cost of a cell on the open list
    int Gcost[][] = new int[mapWidth + 1][mapHeight + 1]; 	//2d array to store G cost for each cell.
    int Hcost[] = new int[mapWidth * mapHeight + 2];	//1d array to store H cost of a cell on the open list
    int pathLength;     //stores length of the found path for critter
    int pathLocation;   //stores current position along the chosen path for critter		
    //int* pathBank [numberPeople+1];
    Vector pathBank = new Vector();
    //Path reading variables
    int pathStatus;
    int xPath;
    int yPath;
    Map themap;

    public Pathfinder(Map themap) {
        //this.themap = themap;
        if (themap != null);
        this.themap = themap;
    }
//-----------------------------------------------------------------------------
// Function Prototypes: where needed
//-----------------------------------------------------------------------------
/*void ReadPath(int pathfinderID,int currentX,int currentY, int pixelsPerFrame);
    int ReadPathX(int pathfinderID,int pathLocation);
    int ReadPathY(int pathfinderID,int pathLocation);*///-----------------------------------------------------------------------------
// Name: InitializePathfinder
// Desc: Allocates memory for the pathfinder.
//-----------------------------------------------------------------------------
    void InitializePathfinder() {
        /*for (int x = 0; x < numberPeople+1; x++)
        pathBank [x] = (int*) malloc(4);*/
    }
//-----------------------------------------------------------------------------
// Name: EndPathfinder
// Desc: Frees memory used by the pathfinder.
//-----------------------------------------------------------------------------
    void EndPathfinder() {
        /*for (int x = 0; x < numberPeople+1; x++)
        {
        free (pathBank [x]);
        }*/
    }
//-----------------------------------------------------------------------------
// Name: FindPath
// Desc: Finds a path using A*
//-----------------------------------------------------------------------------
    int FindPath(boolean invertWeights, boolean isTrailblazer, boolean allowDiagonals, int startingX, int startingY,
            int targetX, int targetY) {
        this.maptiles = themap.tilemap;
        this.pathBank.removeAllElements();
        int onOpenList = 0, parentXval = 0, parentYval = 0,
                a = 0, b = 0, m = 0, u = 0, v = 0, temp = 0, corner = 0, numberOfOpenListItems = 0,
                addedGCost = 0, tempGcost = 0, path = 0,
                tempx, pathX, pathY, cellPosition,
                newOpenListItemID = 0;
//1. Convert location data (in pixels) to coordinates in the walkability array.
        int startX = startingX;
        int startY = startingY;


//2.Quick Path Checks: Under the some circumstances no path needs to
//	be generated ...

//	If starting location and target are in the same location...
        if (startX == targetX && startY == targetY) {
            return found;
        }
        if (startX == targetX && startY == targetY) {
            return nonexistent;//	If target square is unwalkable,or there's an actor in the way
//      return that it's a nonexistent path.
        }
        if (maptiles[targetX][targetY].getTileType() == Constants.TILE_UNPASSABLE) {
            xPath = startingX;
            yPath = startingY;
            return nonexistent;
        }

//3.Reset some variables that need to be cleared
        if (onClosedList > 1000000) //reset whichList occasionally
        {
            for (int x = 0; x < mapWidth; x++) {
                for (int y = 0; y < mapHeight; y++) {
                    whichList[x][y] = 0;
                }
            }
            onClosedList = 10;
        }
        onClosedList = onClosedList + 2; //changing the values of onOpenList and onClosed list is faster than redimming whichList() array
        onOpenList = onClosedList - 1;
        pathLength = notStarted;//i.e, = 0
        pathLocation = notStarted;//i.e, = 0
        Gcost[startX][startY] = 0; //reset starting square's G value to 0

//4.Add the starting location to the open list of squares to be checked.
        numberOfOpenListItems = 1;
        openList[1] = 1;//assign it as the top (and currently only) item in the open list, which is maintained as a binary heap (explained below)
        openX[1] = startX;
        openY[1] = startY;

//5.Do the following until a path is found or deemed nonexistent.
        do {

//6.If the open list is not empty, take the first cell off of the list.
//	This is the lowest F cost cell on the open list.
            if (numberOfOpenListItems != 0) {

//7. Pop the first item off the open list.
                parentXval = openX[openList[1]];
                parentYval = openY[openList[1]]; //record cell coordinates of the item
                whichList[parentXval][parentYval] = onClosedList;//add the item to the closed list

//	Open List = Binary Heap: Delete this item from the open list, which
//  is maintained as a binary heap. For more information on binary heaps, see:
//	http://www.policyalmanac.org/games/binaryHeaps.htm
                numberOfOpenListItems = numberOfOpenListItems - 1;//reduce number of open list items by 1	

//	Delete the top item in binary heap and reorder the heap, with the lowest F cost item rising to the top.
                openList[1] = openList[numberOfOpenListItems + 1];//move the last item in the heap up to slot #1
                v = 1;

//	Repeat the following until the new item in slot #1 sinks to its proper spot in the heap.
                do {
                    u = v;
                    if (2 * u + 1 <= numberOfOpenListItems) //if both children exist
                    {
                        //Check if the F cost of the parent is greater than each child.
                        //Select the lowest of the two children.
                        if (Fcost[openList[u]] >= Fcost[openList[2 * u]]) {
                            v = 2 * u;
                        }
                        if (Fcost[openList[v]] >= Fcost[openList[2 * u + 1]]) {
                            v = 2 * u + 1;
                        }
                    }
                    else {
                        if (2 * u <= numberOfOpenListItems) //if only child #1 exists
                        {
                            //Check if the F cost of the parent is greater than child #1	
                            if (Fcost[openList[u]] >= Fcost[openList[2 * u]]) {
                                v = 2 * u;
                            }
                        }
                    }

                    if (u != v) //if parent's F is > one of its children, swap them
                    {
                        temp = openList[u];
                        openList[u] = openList[v];
                        openList[v] = temp;
                    }
                    else {
                        break; //otherwise, exit loop
                    }
                } while (true);//reorder the binary heap


//7.Check the adjacent squares. (Its "children" -- these path children
//	are similar, conceptually, to the binary heap children mentioned
//	above, but don't confuse them. They are different. Path children
//	are portrayed in Demo 1 with grey pointers pointing toward
//	their parents.) Add these adjacent child squares to the open list
//	for later consideration if appropriate (see various if statements
//	below).
                for (b = parentYval - 1; b <= parentYval + 1; b++) {
                    for (a = parentXval - 1; a <= parentXval + 1; a++) {

                        //if we don't want diagonals
                        if (!allowDiagonals) {
                            //then skip all the diagonal cases, there must be a better way 
                            //to do this
                            if ((b == parentYval - 1 && a == parentXval - 1) ||
                                    (b == parentYval + 1 && a == parentXval - 1) ||
                                    (b == parentYval - 1 && a == parentXval + 1) ||
                                    (b == parentYval + 1 && a == parentXval + 1)) {
                                continue;
                            }
                        }
//	If not off the map (do this first to avoid array out-of-bounds errors)
                        if (a != -1 && b != -1 && a != mapWidth && b != mapHeight) {

//	If not already on the closed list (items on the closed list have
//	already been considered and can now be ignored).			
                            if (whichList[a][b] != onClosedList) {

//	If not a wall/obstacle square and not full of an actor
                                //TODO: find out a way for actors to go around other actors without blocking themselves with themselves
                                if ((maptiles[a][b].getTileType() != Constants.TILE_UNPASSABLE) || isTrailblazer) {

//	Don't cut across corners
                                    corner = walkable;

                                    if (a == parentXval - 1) {
                                        if (b == parentYval - 1) {
                                            if (maptiles[parentXval - 1][parentYval].getTileType() == unwalkable || maptiles[parentXval][parentYval - 1].getTileType() == unwalkable) {
                                                corner = unwalkable;
                                            }
                                        }
                                        else if (b == parentYval + 1) {
                                            if (maptiles[parentXval][parentYval + 1].getTileType() == unwalkable || maptiles[parentXval - 1][parentYval].getTileType() == unwalkable) {
                                                corner = unwalkable;
                                            }
                                        }
                                    }
                                    else if (a == parentXval + 1) {
                                        if (b == parentYval - 1) {
                                            if (maptiles[parentXval][parentYval - 1].getTileType() == unwalkable || maptiles[parentXval + 1][parentYval].getTileType() == unwalkable) {
                                                corner = unwalkable;
                                            }
                                        }
                                        else if (b == parentYval + 1) {
                                            if (maptiles[parentXval + 1][parentYval].getTileType() == unwalkable || maptiles[parentXval][parentYval + 1].getTileType() == unwalkable) {
                                                corner = unwalkable;
                                            }
                                        }
                                    }
                                    if (corner == walkable) {

//	If not already on the open list, add it to the open list.			
                                        if (whichList[a][b] != onOpenList) {

                                            //Create a new open list item in the binary heap.
                                            newOpenListItemID = newOpenListItemID + 1; //each new item has a unique ID #
                                            m = numberOfOpenListItems + 1;
                                            openList[m] = newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap
                                            openX[newOpenListItemID] = a;
                                            openY[newOpenListItemID] = b;//record the x and y coordinates of the new item

                                            //Figure out its G cost
                                            if (Math.abs(a - parentXval) == 1 && Math.abs(b - parentYval) == 1) {
                                                addedGCost = 14;//cost of going to diagonal squares	
                                            }
                                            else {
                                                addedGCost = 10;//cost of going to non-diagonal squares				
                                            }
                                            Gcost[a][b] = Gcost[parentXval][parentYval] + addedGCost;

                                            //Figure out its H and F costs and parent
                                            if (invertWeights) {
                                                Hcost[openList[m]] = maptiles[a][b].getTileType() + (Math.abs(a - targetX) + Math.abs(b - targetY));
                                            }
                                            else {
                                                Hcost[openList[m]] = maptiles[a][b].getTileType() * (Math.abs(a - targetX) + Math.abs(b - targetY));
                                            //Hcost[openList[m]] = 10*(Math.abs(a - targetX) + Math.abs(b - targetY));
                                            }
                                            Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]];
                                            parentX[a][b] = parentXval;
                                            parentY[a][b] = parentYval;

                                            //Move the new open list item to the proper place in the binary heap.
                                            //Starting at the bottom, successively compare to parent items,
                                            //swapping as needed until the item finds its place in the heap
                                            //or bubbles all the way to the top (if it has the lowest F cost).
                                            while (m != 1) //While item hasn't bubbled to the top (m=1)	
                                            {
                                                //Check if child's F cost is < parent's F cost. If so, swap them.	
                                                if (Fcost[openList[m]] <= Fcost[openList[m / 2]]) {
                                                    temp = openList[m / 2];
                                                    openList[m / 2] = openList[m];
                                                    openList[m] = temp;
                                                    m = m / 2;
                                                }
                                                else {
                                                    break;
                                                }
                                            }
                                            numberOfOpenListItems = numberOfOpenListItems + 1;//add one to the number of items in the heap

                                            //Change whichList to show that the new item is on the open list.
                                            whichList[a][b] = onOpenList;
                                        }//8.If adjacent cell is already on the open list, check to see if this 
//	path to that cell from the starting location is a better one. 
//	If so, change the parent of the cell and its G and F costs.	
                                        else //If whichList(a,b) = onOpenList
                                        {

                                            //Figure out the G cost of this possible new path
                                            if (Math.abs(a - parentXval) == 1 && Math.abs(b - parentYval) == 1) {
                                                addedGCost = 14;//cost of going to diagonal tiles	
                                            }
                                            else {
                                                addedGCost = 10;//cost of going to non-diagonal tiles				
                                            }
                                            tempGcost = Gcost[parentXval][parentYval] + addedGCost;

                                            //If this path is shorter (G cost is lower) then change
                                            //the parent cell, G cost and F cost. 		
                                            if (tempGcost < Gcost[a][b]) //if G cost is less,
                                            {
                                                parentX[a][b] = parentXval; //change the square's parent
                                                parentY[a][b] = parentYval;
                                                Gcost[a][b] = tempGcost;//change the G cost			

                                                //Because changing the G cost also changes the F cost, if
                                                //the item is on the open list we need to change the item's
                                                //recorded F cost and its position on the open list to make
                                                //sure that we maintain a properly ordered open list.
                                                for (int x = 1; x <= numberOfOpenListItems; x++) //look for the item in the heap
                                                {
                                                    if (openX[openList[x]] == a && openY[openList[x]] == b) //item found
                                                    {
                                                        Fcost[openList[x]] = Gcost[a][b] + Hcost[openList[x]];//change the F cost

                                                        //See if changing the F score bubbles the item up from it's current location in the heap
                                                        m = x;
                                                        while (m != 1) //While item hasn't bubbled to the top (m=1)	
                                                        {
                                                            //Check if child is < parent. If so, swap them.	
                                                            if (Fcost[openList[m]] < Fcost[openList[m / 2]]) {
                                                                temp = openList[m / 2];
                                                                openList[m / 2] = openList[m];
                                                                openList[m] = temp;
                                                                m = m / 2;
                                                            }
                                                            else {
                                                                break;
                                                            }
                                                        }
                                                        break; //exit for x = loop
                                                    } //If openX(openList(x)) = a
                                                } //For x = 1 To numberOfOpenListItems
                                            }//If tempGcost < Gcost(a,b)

                                        }//else If whichList(a,b) = onOpenList	
                                    }//If not cutting a corner
                                }//If not a wall/obstacle square.
                            }//If not already on the closed list 
                        }//If not off the map
                    }//for (a = parentXval-1; a <= parentXval+1; a++){
                }//for (b = parentYval-1; b <= parentYval+1; b++){

            }//if (numberOfOpenListItems != 0)

//9.If open list is empty then there is no path.	
            else {
                path = nonexistent;
                break;
            }

            //If target is added to open list then path has been found.
            if (whichList[targetX][targetY] == onOpenList) {
                path = found;
                break;
            }

        } while (true);//Do until path is found or deemed nonexistent

//10.Save the path if it exists.
        if (path == found) {

//a.Working backwards from the target to the starting location by checking
//	each cell's parent, figure out the length of the path.
            pathX = targetX;
            pathY = targetY;
            do {
                //Look up the parent of the current cell.	
                tempx = parentX[pathX][pathY];
                pathY = parentY[pathX][pathY];
                pathX = tempx;

                //Figure out the path length
                pathLength = pathLength + 1;
            } while (pathX != startX || pathY != startY);

//b.Resize the data bank to the right size in bytes
/*pathBank[pathfinderID] = (int*) realloc (pathBank[pathfinderID],
            pathLength[pathfinderID]*8);*/
//c. Now copy the path information over to the databank. Since we are
//	working backwards from the target to the start location, we copy
//	the information to the data bank in reverse order. The result is
//	a properly ordered set of path data, from the first step to the
//	last.
            pathX = targetX;
            pathY = targetY;
            cellPosition = pathLength * 2;//start at the end	
            do {
                cellPosition = cellPosition - 2;//work backwards 2 integers
                //pathBank[pathfinderID] [cellPosition] = pathX;
                //pathBank[pathfinderID] [cellPosition+1] = pathY;
                Point2d temppoint = new Point2d(pathX, pathY);
                pathBank.addElement(temppoint);
//d.Look up the parent of the current cell.	
                tempx = parentX[pathX][pathY];
                pathY = parentY[pathX][pathY];
                pathX = tempx;

//e.If we have reached the starting square, exit the loop.	
            } while (pathX != startX || pathY != startY);

//11.Read the first path step into xPath/yPath arrays
        //ReadPath(pathfinderID,startingX,startingY,1);

        }
        return path;


//13.If there is no path to the selected target, set the pathfinder's
//	xPath and yPath equal to its current location and return that the
//	path is nonexistent.

    }

    public Vector getPath() {
        return pathBank;
    }//=
}

	

